$Spaly$ 是不会用的,这辈子也不会用的。
这道题当然可以用 $Splay$ 做,然而不会。
于是考虑怎么来做这道题,我们先来观察一下所有的操作:
1.插入操作:很普通的插入操作……
2.单旋最小值:
结点的深度的变化如下:
- 需要旋转的结点 $(4)$ :变为 $root$ ,深度变为 $1$ 。
- 需要旋转的结点的子树 $(7)$ :深度不变。
- 其他结点 $(1,2,3,5,6)$ :深度加 $1$ 。
3.单旋最大值:
变化和上面的 “单旋最小值” 一样。
4.5 删除最大/最小值
先将需要删除的 最大/最小值 转到树根,这个时候我们将树根删掉,可以发现整棵树的深度全部都减了 $1$ ,一起计算上旋转造成的深度的影响会得到:
- 删掉的结点的子树 $(7)$ :深度减 $1$
- 其他节点 $(1,2,3,5,6)$ :深度不变
发现深度的变化也不是很大,于是我们考虑用线段树维护每一个节点的深度。
线段树不易寻找最大/最小值,这个地方我们用 $set$ 来辅助即可,操作的时候更新一下 $set$ 中树的形态就好。
线段树的要求很低,一个很普通的兹磁区间修改的线段树即可:
1 | struct Segment_Tree{ |
1.插入操作的实现:
1 | std::set<int> Spaly; |
2.单旋最小/最大值的实现:
1 | inline int Rotate_min(){ |
3.删除最小/最大值的实现:
1 | inline void Delete_min(){ |
Code:
1 |
|
本文标题:【题解】 [AH2017/HNOI2017]单旋 线段树 luoguP3721/bzoj4825
文章作者:Qiuly
发布时间:2019年03月15日 - 00:00
最后更新:2019年03月29日 - 13:52
原始链接:http://qiulyblog.github.io/2019/03/15/[题解]bzoj4825/
许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。